package com.terry.test3;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

/**
 * 高效的任务规划
 * 题目描述
 * 你有 n 台机器编号为 1~n，每台都需要完成完成一项工作，机器经过配置后都能完成独立完成一项工作。
 * 假设第 i 台机器你需要花 B 分钟进行设置，然后开始运行，J 分钟后完成任务。
 * 现在，你需要选择布置工作的顺序，使得用最短的时间完成所有工作。
 * 注意，不能同时对两台机器进行配置，但配置完成的机器们可以同时执行它们各自的工作。
 * 输入描述：
 *
 * 第一行输入代表总共有 M 组任务数据（1<M<=10）。
 * 每组数第一行为一个整数，指定机器的数量 N（0<N<=1000）。
 * 随后的 N 行每行两个整数，第一个表示 B（0<=B<=10000），第二个表示 J（0<=J<=10000）。
 * 每组数据连续输入，不会用空行分隔。
 * 各组任务单独计时。
 * 输出描述：
 *
 * 对于每组任务，输出最短完成时间，且每组的结果独占一行。
 * 例如，两组任务就应该有两行输出。
 *
 * 输入
 *  1    // 一组任务
 *  1    // 一台机器
 *  2 2   //机器配置需两分钟  机器运行需两分钟
 *
 * 输出
 *  4
 *
 * 输入
 *  2
 *  2
 *  1 1
 *  2 2
 *  3
 *  1 1
 *  2 2
 *  3 3
 *
 * 输出
 *  4
 *  7
 *
 *  题目要求总耗时最短，又因为每次只能配置一台机器，因此我们应该让任务工作时间最长的机器先运行。因此我们先将工作时间降序排列（跟配置时间无关）
 *  那这个配置时间是干啥？配置时间是用来干扰你的。举个例子就知道了
 *  这可以这样想，如果让任务工作时间最短的在前面运行，那么同段时间的时间利用率就不是最高，因此并行时间越多越好，这样才会获得总体最短时间
 *  动态规划：dp[i]表示当前机器工作完成的经过的总时间
 *  转移方程：
 *  因为第i台机器开始配置并工作必须是前i-1台机器都完成了配置，当前机器之前所有机器的总配置时间假设是last，那么第i台机器完成工作所用的总时间为dp[i] = last + machine[i][0] + machine[i][1];
 *  设最短的完成时间res，初始化res=0,last=0，则 res = max(res, dp[i]);
 *
 * @author 小八
 * @date 2023年02月09日14:24
 */
class Machine{
    public int p;
    public int r;
    public Machine(int p,int r){
        this.p = p ;
        this.r = r ;
    }
}

public class Title8 {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNextLine()){
            Integer taskNum = Integer.parseInt(in.nextLine());
            List<Integer> result = new ArrayList<>();
            while(taskNum>0) {
                Integer machineNum = Integer.parseInt(in.nextLine());
                Machine[] machineArr = new Machine[machineNum];
                for (int i = 0; i < machineNum; i++) {
                    String[] splitStr = in.nextLine().split(" ");
                    machineArr[i] = new Machine(Integer.parseInt(splitStr[0]),Integer.parseInt(splitStr[1]));
                }
                Arrays.sort(machineArr,(a,b)->b.r-a.r);
                int[] dp = new int[machineNum];
                int[] pArr = new int[machineNum];
                dp[0] = machineArr[0].p + machineArr[0].r;
                pArr[0] = machineArr[0].p;
                int maxTime = dp[0] ;
                for(int i=1;i<machineNum;i++){
                    dp[i] = pArr[i-1] + machineArr[i].p + machineArr[i].r;
                    pArr[i] = pArr[i-1] +  machineArr[i].p;
                    maxTime = Math.max(dp[i],maxTime);
                }
                taskNum -- ;
                result.add(maxTime);
            }
            result.forEach(System.out::println);
        }
    }
}
